package com.chj.zhongji.class09.test01;

//http://chenxii.cn/2020/02/19/D-DataStructureAndAlgorithm/E-ZuoInterview/56-isCross/
//https://ask.csdn.net/questions/202236
public class Code06_StringCross {
	public static boolean isCross1(String s1, String s2, String ai) {
		if (s1 == null || s2 == null || ai == null) {
			return false;
		}
		char[] str1 = s1.toCharArray();
		char[] str2 = s2.toCharArray();
		char[] aim = ai.toCharArray();
		if (aim.length != str1.length + str2.length) {
			return false;
		}
		boolean[][] dp = new boolean[str1.length + 1][str2.length + 1];
		dp[0][0] = true;
		for (int i = 1; i <= str1.length; i++) {
			if (str1[i - 1] != aim[i - 1]) {
				break;
			}
			dp[i][0] = true;
		}
		for (int j = 1; j <= str2.length; j++) {
			if (str2[j - 1] != aim[j - 1]) {
				break;
			}
			dp[0][j] = true;
		}
		for (int i = 1; i <= str1.length; i++) {
			for (int j = 1; j <= str2.length; j++) {
				if ((str1[i - 1] == aim[i + j - 1] && dp[i - 1][j])
						|| (str2[j - 1] == aim[i + j - 1] && dp[i][j - 1])) {
					dp[i][j] = true;
				}
			}
		}
		return dp[str1.length][str2.length];
	}

	public static boolean isCross2(String str1, String str2, String aim) {
		if (str1 == null || str2 == null || aim == null) {
			return false;
		}
		char[] ch1 = str1.toCharArray();
		char[] ch2 = str2.toCharArray();
		char[] chaim = aim.toCharArray();
		if (chaim.length != ch1.length + ch2.length) {
			return false;
		}
		char[] longs = ch1.length >= ch2.length ? ch1 : ch2;
		char[] shorts = ch1.length < ch2.length ? ch1 : ch2;
		boolean[] dp = new boolean[shorts.length + 1];
		dp[0] = true;
		for (int i = 1; i <= shorts.length; i++) {
			if (shorts[i - 1] != chaim[i - 1]) {
				break;
			}
			dp[i] = true;
		}
		for (int i = 1; i <= longs.length; i++) {
			dp[0] = dp[0] && longs[i - 1] == chaim[i - 1];
			for (int j = 1; j <= shorts.length; j++) {
				if ((longs[i - 1] == chaim[i + j - 1] && dp[j]) || (shorts[j - 1] == chaim[i + j - 1] && dp[j - 1])) {
					dp[j] = true;
				} else {
					dp[j] = false;
				}
			}
		}
		return dp[shorts.length];
	}

	public static boolean chkMixture(String A, String B, String C) {
		// write code here
		return chkMixture(A, B, C, A.length() - 1, B.length() - 1, C.length() - 1);
	}

	public static boolean chkMixture(String A, String B, String C, int i, int j, int k) {
		if (k == 0) {
			return true;
		}
		if (i == 0) {
			if (B.charAt(j) == C.charAt(k)) {
				return chkMixture(A, B, C, 0, j - 1, k - 1);
			} else {
				return false;
			}
		}
		if (j == 0) {
			if (A.charAt(i) == C.charAt(k)) {
				return chkMixture(A, B, C, i - 1, 0, k - 1);
			} else {
				return false;
			}
		}
		boolean res1 = false;
		boolean res2 = false;
		if (A.charAt(i) == C.charAt(k)) {
			res1 = chkMixture(A, B, C, i - 1, j, k - 1);
		}
		if (B.charAt(j) == C.charAt(k)) {
			res2 = chkMixture(A, B, C, i, j - 1, k - 1);
		}

//		return res1 || res2;
		if (res1 || res2) {
			return true;
		} else {
			return false;
		}
	}

	public static boolean chkMixtureDp(String A, String B, String C) {
		char[] aAim = A.toCharArray();
		char[] bAim = B.toCharArray();
		char[] cAim = C.toCharArray();
		int i = aAim.length - 1;
		int j = bAim.length - 1;

		boolean[][][] dp = new boolean[aAim.length][bAim.length][cAim.length];

		for (int k = cAim.length - 1; k >= 0; k--) {
			if (k == 0) {
				dp[i][j][k] = true;
			}

			if (i == 0 && j > 0) {
				if (bAim[j] == cAim[k]) {
					dp[0][j - 1][k - 1] = true;
					j--;
				} else {
					return false;
				}
			}
			if (j == 0 && i > 0) {
				if (aAim[i] == cAim[k]) {
					dp[i - 1][0][k - 1] = true;
					i--;
				} else {
					return false;
				}
			}

			if (aAim[i] == cAim[k]) {
				if (i > 0) {
					dp[i - 1][j][k - 1] = true;
					i--;
				}
			}
			if (bAim[j] == cAim[k]) {
				if (j > 0) {
					dp[i][j - 1][k - 1] = true;
					j--;
				}
			}
		}

		return dp[0][0][0];
	}

	public static void main(String[] args) {
		String str1 = "1234";
		String str2 = "abcd";
		String aim = "1a23bcd4";
		System.out.println(isCross1(str1, str2, aim));
		System.out.println(isCross2(str1, str2, aim));
		System.out.println(chkMixture(str1, str2, aim));
		System.out.println(chkMixtureDp(str1, str2, aim));
		System.out.println(true || true);
		System.out.println(true || false);
		System.out.println(false || false);
	}
}
